#include <cstdio>
#include <random>
#include <numeric>
#include <algorithm>
#include <chrono>


class TimeCost {
public:
    TimeCost() {
        start_point = std::chrono::steady_clock::now();
    }
    ~TimeCost() {

        using namespace std::chrono;
        duration<double> d = duration_cast<duration<double> >(steady_clock::now() - start_point); 
        printf("Program Cost %lf s", d.count());
    }

private:

    std::chrono::steady_clock::time_point start_point;
};

double solve_prisoners()
{
    double ans = 0;
    for (int i = 51;i < 101;i++) {
        ans += (double) 1.0 / i;
    }

    return 1 - ans;
}
int getMaxCircle(const std::vector<int> &p)
{
    std::vector<int> vis(p.size(), 0);
    int ans = 1;

    for (int i = 0; i < 100;i++) {
        if (!vis[i]) {
            int node_cnt = 0;
            for (int j = i;!vis[j];j = p[j]) {
                vis[j] = 1;
                node_cnt++;
            }
            ans = std::max(ans, node_cnt);
        }
    }
    return ans;
}
void gen_perm(std::vector<int> &pNum)
{
    std::random_device rd;  // a seed source for the random number engine
    std::mt19937 gen(rd()); // mersenne_twister_engine seeded with rd()
    // int cnt = 99;
    // for (int cnt = 99; cnt ; --cnt) {   
    //     std::uniform_int_distribution<> distrib(0, cnt);
    //     int xth = distrib(gen);
    //     std::swap(pNum[xth], pNum[cnt]);

    // }
    std::shuffle(pNum.begin(), pNum.end(),  gen);
}
double prisoners_success(int n)
{
    std::random_device rd;  // a seed source for the random number engine
    std::mt19937 gen(rd()); // mersenne_twister_engine seeded with rd()
    std::vector<int> pNum(100, 0);
    std::vector<int> vis(100, 0);
    int failure_cnt = 0;
    for (int i = 0;i < n;++i) {            
        std::iota(pNum.begin(), pNum.end(), 0);
        std::shuffle(pNum.begin(), pNum.end(),  gen);
        std::fill(vis.begin(), vis.end(), 0);
        
        int max_circle = 1;
        for (int i = 0; i < 100;i++) {
            if (!vis[i]) {
                int node_cnt = 0;
                for (int j = i;!vis[j];j = pNum[j]) {
                    vis[j] = 1;
                    node_cnt++;
                }
                max_circle = std::max( max_circle, node_cnt);
            }
        }
        if ( max_circle > 50)
            failure_cnt++;
    }
    return (double) 1.0 - (double) failure_cnt / n;
}
int main()
{
    TimeCost tm_cost;
    printf("probablity: %.6lf\n", solve_prisoners());
    int nTests = 10000000;
    printf("simi %d tests probablility: %.6lf\n", nTests, prisoners_success(nTests));
    return 0;
}